The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
Scheduling of packets in network systems is done based on many criteria. Generally, there are many individual queues of packets, arranged in some hierarchical fashion based on their properties and/or interfaces. A scheduler attempts to serve each of the leaf queues (and each of the aggregated nodes in the hierarchy above the leaves) fairly, where the definition of “fair” is usually based on delivered bandwidth. To do this, current schedulers use the exact length (in bytes) of each packet as it is scheduled, and this information must be saved for each packet in each queue. In a typical system running at 10 Gbps, there could be as many as 4M packets present. Each of which must have an associated packet length. With an approximate 10K maximum transfer unit (MTU), each packet length would require 14 bits, and storing 4M packet lengths would require 56 Mb of storage. While this amount of storage is small compared to the actual packet data, the packet lengths must generally be saved in faster (and more expensive) SRAM control structures (for ease and latency of access), as compared to the bulk DRAM generally used to hold the packet data. Using a packet length, the scheduler can determine how much traffic a given queue consumed in sending that particular packet, and can decide based on this when next to serve that queue in relation to all other queues.
The scheduling problem is very complex due to many different constraints used in defining what is fair, and due to the hierarchical nature of the scheduling problem, as the scheduler must be fair at each layer of the hierarchical scheduling tree. Doing scheduling generally calls for some amount of math performed on the packet lengths. For example, updating token buckets, or computing next service times, and these computations must be done at all layers of the scheduling hierarchy. Furthermore, there are large numbers of queues, each of which must store and track packet lengths. Simply using packet lengths with less resolution (e.g., fewer bits such as by dropping some number of low-order bits) would simplify the implementation significantly, but this cannot be done because any loss of precision in the packet lengths will result in accumulated errors in the scheduling process.
For example, packet lengths are nominally 14 bits (to support an approximate 10K MTU). If the scheduler only used the upper 8 bits, each packet scheduled could be off by between 0 and 63 bytes. This would lead to a very large accumulated error in a very short time. What is desired is a means to shorten the packet lengths associated with each packet and seen by the scheduler without accumulating any long-term errors in the amount of data being scheduled.